//
// Created by Administrator on 2021/6/3.
//

//给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int findMaxLength(vector<int> &nums) {
        // hash  +  前缀和
        // 0:-1  1:+1
        // 出现相同的前缀和时,之间的是满足条件的连续子数组
        unordered_map<int, int> mp;
        mp[0] = -1;
        int preSum = 0;
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 0) --preSum;
            else ++preSum;
            if (mp.find(preSum) != mp.end()) {
                ans = max(ans, i - mp[preSum]);
            } else mp[preSum] = i;
        }
        return ans;
    }
};


int main() {
    vector<int> nums{0, 1,1,0,1,1,1};
    Solution sol;
    cout << sol.findMaxLength(nums) << endl;
    return 0;
}